from LeetCoder import *


class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l = [0] * n
        r = [0] * n
        s = set()
        diff = 0
        for i in range(n):
            num = nums[i]
            if num not in s:
                diff += 1
                s.add(num)
            l[i] = diff
        s = set()
        r[n - 1] = 0
        s.add(nums[n-1])
        diff = 1
        for i in range(n - 2, -1, -1):
            num = nums[i]
            r[i] = diff
            if num not in s:
                diff += 1
                s.add(num)
        ans = [0] * n
        for i in range(n):
            ans[i] = l[i] - r[i]
        return ans

s = Solution()
print(s.distinctDifferenceArray([37, 37, 37, 37, 33]) == [-1, -1, -1, 0, 2])
print(s.distinctDifferenceArray([1, 2, 3, 4, 5]) == [-3, -1, 1, 3, 5])
print(s.distinctDifferenceArray([3, 2, 3, 4, 2]) == [-2, -1, 0, 2, 3])
